package com.success.fenbi;

import org.junit.Test;

/**
 * @Author: 小混蛋
 * @CreateDate: 2018/12/20 15:13
 * @Desc：迷宫问题，深度搜索
 */
public class TheMazeDfs {
    boolean result;
    public boolean dfs(int x, int y, boolean[][] maze, int[][] used, int[][] next) {
        if (x == maze.length - 1 && y == maze[0].length - 1) {
            result = true;
            System.out.println(result);
            return result;
        }
        int posx, posy;
        for (int i = 0; i <= 3; i++) {
            posx = x + next[i][0];
            posy = y + next[i][1];
            if (posx < 0 || posx > maze.length - 1 || posy < 0 || posy > maze[0].length - 1) {
                continue;
            }
            if (maze[posx][posy] && used[posx][posy] == 0) {
                used[posx][posy] = 1;
                dfs(posx, posy, maze, used, next);
                used[posx][posy] = 0;
            }
        }
        return result;
    }

    @Test
    public void test() {
        boolean[][] maze = new boolean[5][4];
        maze[0][0] = true;
        maze[0][1] = true;
        maze[1][1] = false;
        maze[1][2] = true;
        maze[2][2] = true;
        maze[3][2] = true;
        maze[4][2] = true;
        maze[4][3] = true;
        for (boolean[] row : maze) {
            for (boolean node : row) {
                System.out.print(node + "\t");
            }
            System.out.println("\b");
        }
        int[][] next = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        System.out.println(dfs(0, 0, maze, new int[5][4], next));
    }
}